#include <stdio.h>
#include <cstring>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <time.h>

const int N = 100;
const int INFINITY = N;
#define M(i,j) m[(i)*N+(j)]

using namespace std;

int out_graph(int n)
{
	srand(time(NULL));
	int * m = new int[n*n];
	int k = 0;
	for(int i = 0;i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j)
				M(i,j) = 0;
			else
				M(i,j) = INFINITY;
		}
	}
	for(int i = 0;i < n; i++){
		for(int j = 0; j < n / 3; j++){
			int dst = (i+rand()) % n;
			if(dst != i){
				int r = rand() % 3;
				r = (r == 0) ? 1 : INFINITY;
				M(i,dst) = M(dst,i) = r;
			}
		}
	}		
	FILE *f = fopen("graph.txt","w");
	for(int i = 0;i < n; i++){
		for(int j = i+1; j < n; j++)
		{
			if(M(i,j) != INFINITY)
			{
				fprintf(f,"%d %d\n",i,j);
				k++;
			}
		}
	}
	free(m);
	fclose(f);
	return k;
}

vector<double> solve 
(int n, int m, vector<vector<int> > e)
{
    vector<double> Cb(n, 0);

    for (int s = 0; s < n; s ++)
    {
        stack<int> S;
        vector<list<int> > P(n);
        vector<int> sigma (n, 0);   sigma[s] = 1;
        vector<int> d (n, -1);      d[s] = 0;
        queue<int> Q;

        Q.push(s);
        while (!Q.empty())
        {
            int v = Q.front ();
            Q.pop ();

            S.push(v);

            for (vector<int>::iterator it = e[v].begin(); it != e[v].end(); ++it)
            {
                int w = *it;
                if (d[w] < 0)
                {
                    Q.push (w);
                    d[w] = d[v] + 1;
                }

                if (d[w] == d[v] + 1)
                {
                    sigma[w] = sigma[w] + sigma[v];
                    P[w].push_back (v);
                }
            }
        }

        vector<double> delta (n, 0);
        while (!S.empty())
        {			
            int w = S.top ();
            S.pop ();
            for (list<int>::iterator it = P[w].begin(); it != P[w].end(); ++ it)
            {
                int v = *it;
                delta[v] = delta[v] + sigma[v] / (double)(sigma[w]) * (1 + delta[w]);
            }
            if (w != s)
                Cb[w] = Cb[w] + delta[w];
        }
    }
    
    return Cb;
}

int main ()
{	
    int m = out_graph(N);	
    vector<vector<int> > e;
	ifstream fin("graph.txt");

    vector<int> a (m);
    vector<int> b (m);
    vector<int> x (m * 2);
    for (int i = 0; i < m; i ++)
    {
        fin >> a[i] >> b[i];
        x [i * 2] = a[i];
        x [i * 2 + 1] = b[i];
    }
    sort(x.begin(), x.end());
    int n = unique(x.begin(), x.end()) - x.begin();
    
    x.resize(n);
    e.resize(n);

    for (int i = 0; i < m; i ++)
    {
        int aa = lower_bound(x.begin(), x.end(), a[i]) - x.begin();
        int bb = lower_bound(x.begin(), x.end(), b[i]) - x.begin();

        e[aa].push_back(bb);
        e[bb].push_back(aa);
    }
    
    vector<double> Cb = solve(n, m, e);
    for (int i = 0; i < n; i ++)
		cout << x[i] << "\t" << Cb[i] / 2 << endl;

    return 0;
}
